Block storage is a common method of managing storage on disk drives, in which a minimum unit of storage is a fixed-size block. When using block storage to store files, a single file typically occupies multiple blocks. When files are deleted, this creates gaps in block storage. It is often beneficial to be able to easily find gaps of a given size, for example, when adding a new file of a given size to block storage. One way to manage gaps in disk storage is to use a free space bitmap, a bit array in which the bits indicate whether the corresponding block is available or unavailable. For example, a 4 GB disk with 4096 byte sectors would require 1,048,576 bits for the free space bitmap.
Using the free space bitmap approach, finding a gap of a particular size requires traversing the bitmap until a gap of a particular size is located. When the disk is nearly empty, this approach works well in some systems, but becomes inefficient when the disk is nearly full. Thus, for systems that typically operate at nearly-full capacity for any significant time, a more efficient approach is desirable.